﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

//class Solution {
//public:
//    bool isMatch(string s, string p) {
//        int n = s.size(), m = p.size();
//        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
//        //for (int i = 0; i < m + 1; i++) dp[0][i] = true;
//        //for (int i = 0; i < n + 1; i++) dp[i][0] = true;
//        dp[0][0] = true;
//        for (int i = 1; i <= m; i++)
//        {
//            if (p[i - 1] == '*') dp[0][i] = true;
//            else break;
//        }
//
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= m; j++)
//            {
//                if (p[j - 1] == s[i - 1] || p[j - 1] == '?')
//                {
//                    dp[i][j] = dp[i - 1][j - 1];
//                }
//                else if (p[j - 1] == '*')
//                {
//                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
//                }
//            }
//        }
//        return dp[n][m];
//    }
//};


//class Solution {
//public:
//    bool isMatch(string s, string p) {
//        int n = s.size(), m = p.size();
//        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
//        for (int i = 0; i <= m; i++) dp[0][i] = true;
//        int x = p.rfind('*');
//        if (x == string::npos)
//        {
//            x = 1;
//        }
//        else
//        {
//            if (x >= n - 1) return true;
//            for (int i = 1; i <= x + 1; i++) dp[i][i] = true;
//            x += 2;
//        }
//        for (int i = x; i <= n; i++)
//        {
//            for (int j = x; j <= m; j++)
//            {
//                if (p[j] == '.' || p[j] == s[i]) dp[i][j] = dp[i - 1][j - 1];
//                else if (s[i] != p[j]) dp[i][j] = dp[i][j - 1];
//            }
//        }
//        return dp[n][m];
//    }
//};


//class Solution {
//public:
//    bool isMatch(string s, string p) {
//        int n = s.size(), m = p.size();
//        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
//        dp[0][0] = true;
//        //s = ' ' + s, p = ' ' + p;
//        //if (m > 1) dp[0][2] = p[1] == '*';
//        for (int i = 2; i <= m; i += 2)
//        {
//            if (p[i - 1] == '*') dp[0][i] = true;
//            else break;
//        }
//
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= m; j++)
//            {
//                if (p[j - 1] == '*')
//                {
//                    if (p[j - 2] == '.')
//                    {
//                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
//                    }
//                    else
//                    {
//                        dp[i][j] = dp[i][j - 2] || p[j - 2] == s[i - 1] && dp[i - 1][j];
//                    }
//                }
//                else
//                {
//                    if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
//                }
//            }
//        }
//        return dp[n][m];
//    }
//};